package com.yitiao.data_algorithms.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

class FindLongestSubarrayLcci{
    // 2024-02-20 18:54:40
    public static void main(String[] args) {
        Solution solution = new FindLongestSubarrayLcci().new Solution();
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String[] findLongestSubarray(String[] array) {
        int n = array.length;
        int[] s = new int[n + 1]; // 前缀和
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + (array[i].charAt(0) >> 6 & 1) * 2 - 1;
        }
        int begin = 0, end = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int j = 0; j < s.length; j++) {
            if (!map.containsKey(s[j])) {
                map.put(s[j], j);
            } else {
                if ((end - begin) < (j - map.get(s[j]))) {
                    begin = map.get(s[j]);
                    end = j;
                }
            }
        }
        String[] ans = new String[end - begin];
        System.arraycopy(array, begin, ans, 0, ans.length);
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}